Convex body collision detection using the signed distance function

P. López-Adeva Fernández-Layos, L.F. S. Merchante

Computer-Aided Design Vol. 170, pp. 103685-1 - 103685-16

Resumen:

We present a new algorithm to compute the minimum distance and penetration depth between two convex bodies represented by their Signed Distance Function (SDF). First, we formulate the problem as an optimization problem suitable for arbitrary non-convex bodies, and then we propose the ellipsoid algorithm to solve the problem when the two bodies are convex. Finally, we benchmark the algorithm and compare the results in collision detection against the popular Gilbert–Johnson–Keerthi (GJK) and Minkowski Portal Refinement (MPR) algorithms, which represent bodies using the support function. Results show that our algorithm has similar performance to both, providing penetration depth like MPR and, with better robustness, minimum distance like GJK. Our algorithm provides accurate and fast collision detection between implicitly modeled convex rigid bodies and is able to substitute existing algorithms in previous applications whenever the support function is replaced with the SDF.

Resumen divulgativo:

El artículo describe un algoritmo para determinar la distancia mínima y la profundidad de penetración entre cuerpos convexos usando la Signed Distance Function (SDF), superando al algoritmo de Gilbert–Johnson–Keerthi (GJK) y al Minkowski Portal Refinement (MPR) en la detección de colisiones.

Palabras Clave: Signed distance function; Collision detection; Ellipsoid method

Índice de impacto JCR y cuartil WoS: 4,300 - Q1 (2022)

Referencia DOI: https://doi.org/10.1016/j.cad.2024.103685

Publicado en papel: Mayo 2024.

Publicado on-line: Febrero 2024.

Cita:
P. López-Adeva Fernández-Layos, L.F. S. Merchante, Convex body collision detection using the signed distance function. Computer-Aided Design. Vol. 170, pp. 103685-1 - 103685-16, Mayo 2024. [Online: Febrero 2024]